package string.滑动窗口;

import java.util.HashMap;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 无重复字符最长子串.java
 * @Description TODO https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * @createTime 2021年03月02日 13:29:00
 */
public class 无重复字符最长子串 {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("tmmzuxt"));
    }
    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度
     *
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3
     *
     *
     *
     * 解法：滑动窗口
     *
     *
     * 指针start和end 开始时候都指向0，end从字符串第一个字符开始往后前进。如果遇到与区间内的字符串中相同的字符，则把起始位置设置为重复位置的字符。每遍历一个字符，都要计算对应的最长字符串的长度
     *
     */

    public static int lengthOfLongestSubstring(String s) {
        if (s==null || s.isEmpty()){
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int length = s.length();
        int max=0,start=0,end=0;
        for (int i = 1; i < length+1; i++) {
            char code = s.charAt(i-1);
            //如果map  不包含   对应的字符串，则放进去
            if (!map.containsKey(code)){
                map.put(code,i);
            }else {
                //如果map  包含  对应的字符串，把start的值改成重复的值得位置+1。 要+1是因为重复的时候需要减去一个，比如 abca重复之后start开始的位置应该从b开始
                start=Math.max(map.get(code),start);
                map.put(code,i);
            }
            //设置end的值
            end=i;
            //计算最大值
            max=Math.max(max,end-start);
        }
        return max;
    }
}
